package graph_depth_first_travelsal_apply.simple_source_path;

import graph_depth_first_traversal.Graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

/**
 * @author sijunqiang
 * @data 2021/6/15 22:16
 * @description: 单源路径问题
 */
public class SingleSourcePath {

    // 定义一个图属性
    private Graph G;

    // 定义一个布尔数组 用来记录 图中的顶点是否遍历过
    // 这样设计的巧妙之处,在于数组的索引就代表顶点,索引上面的值就表示该顶点是否遍历过
    private boolean[] visited;

    // 定义一个int类型数组,用来记录顶点是从那个顶点过来的
    private int[] pre;

    // 定义一个属性 代表源顶点,
    private int source;

    // construction  G-代表图 ,source-代表图中的源点
    public SingleSourcePath(Graph G, int source) {
        G.validateVertex(source);// 先校验顶点
        this.G = G;
        this.source = source;

        visited = new boolean[G.V()];// 先开辟图中顶点的个数长度。 巧妙的是 索引既是顶点
        pre = new int[G.V()];// 记录该顶点是从那个顶点过来的,同样的 索引即使顶点 索引上面的值 就该该顶点是从那个顶点过来的
        dfs(source, source);// 开始深度优先遍历 source:代表源点
    }

    // source-代表图的顶点.  parent-代表这个顶点是从那个顶点过来的
    private void dfs(int vertex, int parent) {
        visited[vertex] = true;// true-代表这个顶点已经遍历过, vertex-即使索引又是图的顶点,true 代表这个顶点已经遍历过
        pre[vertex] = parent;// 用来记录该顶点的是从那个顶点过来的。 vertex-即是使索引又是图中的顶点,parent是索引上面的值 代表该顶点是从那个顶点过来的。

        // 开始深度优先遍历
        for (int w : G.adj(vertex)) {//循环的遍历这个顶点关联的顶点
            if (!visited[w]) {// 如果关联的顶点未被遍历过 那么就以这个顶点为顶点再次遍历
                dfs(w, vertex);
            }
        }
    }


    // 判断到这个顶点是否连接
    public boolean isConnectTo(int target) {
        G.validateVertex(target);
        return visited[target]; //  visited[target] 如果结果=true 说明 目标顶点和源顶点在同一个联通分量上，false-说明不在同一个联通分量上。
    }

    // 求路径
    public Iterable<Integer> path(int target) {
        ArrayList<Integer> resp = new ArrayList<>();
        if (!isConnectTo(target)) {
            return resp;
        }

        // 这块的逻辑非常巧妙, 巧妙点在于 索引就是图的顶点，索引上面的值就是该顶点是从那个顶点过来的
        int cur = target;
        while (cur != source) {
            resp.add(cur);
            cur = pre[cur];
        }
        resp.add(source);
        Collections.reverse(resp);
        return resp;
    }

    public static void main(String[] args) {
        Graph graph = new Graph("graph_depth_first_traversal.txt");
        System.out.println(graph);
        SingleSourcePath ssPath = new SingleSourcePath(graph, 0);
        System.out.println("0->6: " + ssPath.path(6));
        System.out.println("0->5: " + ssPath.path(5));
    }
}
